1. Field of the Invention
The present invention relates generally to rule matching in an m-dimensional universe with each dimension bound by a lower and upper limit value. In one example, this invention relates to the classification of packets, based on the tuple information, in high-speed digital communication networks, where the implementation of the system does not require dedicated hardware other than the computer system.
2. Description of the Related Art
There are many ways of implementing search engines that perform searches based on various types of search criteria. Consider, for example, a dating search engine utilizing several parameters for the actual search such as gender, age, height, weight, and income level. This type of matching system may develop various ways of matching persons and prioritizing the actual findings based on a variety of rules. In some instances, it may be beneficial to identify which rule applies to a particular coordinate in the various parameters.
One of the traditional approaches for this type of search includes a step by step check of each and every rule to determine if they match any or all of the coordinates possible in the system. Although these types of systems are possible, they are inefficient because they require a significant amount of computational power (e.g., CPU time, memory requirements, etc.) to complete within a reasonable amount of time. As the number of parameters and rules increase, so does the complexity of the search, resulting in a need for even more computational power.
Packets of data flow through a network of computers carrying portions of digital information between the different nodes. Broadly, the results of an application running at one node may be sent to a computer at another network node. To establish the transfer of data, the information is packetized and sent over their respective networks. A complete packet communication may be defined as the sending of a packet upstream, from a source computer system, where it proceeds along a communication path, and then downstream to a destination computer. Efficient network management and system administration of computer systems utilizing upstream/downstream packet communications typically require some type of packet content analysis to maintain this efficiency.
A typical packet utilized for computer network communications includes a packet header. A packet header, which is also referred to as a tuple, typically contains several sections comprising a total of 104 bits. A typical 104 bit packet header contains 32 bits for the Internet protocol (“IP”) source, 32 bits for the IP destination, 16 bits for the port source, 16 bits for the port destination, and the last 8 bits to identify the protocol type. Using the above-described configuration, the tuple typically contains information that can be used to identify the source and destination of the packet. In a high-speed network, millions of packets are sent every second. Thus, it is typically necessary to process these packets at wire speed in order to analyze them effectively and efficiently. It is also desirable for the processed packets to arrive at the appropriate destinations “unharmed.” Furthermore, it is desirable to provide these services to low-cost, general computing systems which are typically limited in their ability to efficiently communicate, receive and process packet header information.
A common problem that occurs during processing of an address space, such as the 104 bit tuple, is the inability to effectively process such a large memory address. To accomplish this, traditional systems commonly utilize a variety of hash tables or other techniques. However, these traditional systems typically lack the capability of operating at wire speed while addressing over one million different process flows.
Some of the traditional systems require numerous steps which grow in number, either linearly or exponentially, based on the number of process flows identified. Other systems require complex resources in order to effectively process the data. Commonly, these systems require a search mechanism that is time consuming and is therefore impractical for wire speed applications.
For example, U.S. Pat. No. 5,414,704 (Spinney) describes a method of searching with an N-bit input address hashed into N-bits. Spinney also describes the use of the lower 16-bits of the hashed address to supply pointers to a maximum of seven buckets. However, Spinney's described solution is not suited for network applications, and also does not support processing at wire-speed. The deficiencies of the Spinney system results from that system's utilization of a binary look-up tree, in conjunction with a content addressable memory (CAM) that is used in parallel to a hash function. The Spinney patent is incorporated herein by reference in its entirety for all purposes.
Descriptions of other types of searching methods may be found in U.S. Pat. No. 5,463,777 (Bialokowski et al.) and U.S. Pat. No. 5,574,910 (Bialokowski et al.). These references describe the use of a binary search tree that relies on a software implementation of an associative memory to match packet headers. While both of the Bialokowski et al. patents describe methods of searching nodes, they require extensive computational resources. Both of the Bialokowski et al. patents are incorporated herein by reference in their entirety for all purposes.
In U.S. Pat. No. 5,745,488 (Thompson et al.) another approach to packet processing is described. Thompson et al. describes a system where a packet tuple is checked and compared against a table of packet types. In this system, the table is implemented using a CAM. The packet tuple is classified so that further processing may occur, while another packet, having a different type, is processed on other system resources. The Thompson et al. patent is incorporated herein by reference in its entirety for all purposes.
Another method is discussed in U.S. Pat. No. 5,815,500 (Murono). Murono describes a system having a plurality of CAMs for the detection of certain packet header information, wherein each CAM is preloaded with the appropriate information. This approach is used in an attempt to expedite packet header processing and therefore increase the speed that the packet is processed through the system. However, the Murono approach is limited based upon this system's reliance upon the utilization of CAMs. The Murono patent is incorporated herein by reference in its entirety for all purposes.
Additional methods and techniques for increasing the speed of look-up tables are described in U.S. Pat. No. 6,032,190 (Bremer et al.), U.S. Pat. No. 6,052,683 (Irwin) U.S. Pat. No. 6,111,874 (Kerstein), and in U.S. Pat. No. 6,161,144 (Michels et al.). Some of the disadvantages of these systems and methods relate to their inability to ensue a predictable and limited time period for packet classification. In those systems, packet classification time typically varies from packet to packet, and in most cases is unpredictable, the utilization of these types of methods do not work well in a time sensitive system (e.g., a computer network). Moreover, these traditional systems' extensive use of CAMs further complicates the overall design, resulting in excessive implementation costs. The Bremer et al., Irwin, Kerstein, and Michels et al. patents are incorporated herein by reference in their entirety for all purposes.